\chapter{Вопрос № 22}

Экспоненциальная формула, комбинаторный смысл. Рекуррентное соотношение для коэффициентов производящих функций. Простейшие примеры.

\section{Экспоненицальная формула}

Пусть $a_n$ количеством способов мы можем совершить некоторое действие над $n$-множеством, причем для $n=0$ $a_0 = 0$. Тогда разбить проивзольное $n$ - множество на непустые блоки и совершть над каждым блоком мощности $i$ действие $a_i$ числом способов можно $c_n$ числом способов, где:
\begin{equation}
	H\left(x\right) = \sum_{i=0}^\infty c_i \frac{x^i}{i!} = exp\left(F\left(x\right)\right)
\end{equation}
где
\[
	F\left(x\right) = a_1 x + a_2 \frac{x^2}{2} + a_3 \frac{x^3}{3!} + ...
\]
эта формула называется экспоненциальной формулой.

\section{Примеры}

В комнате находится $n$ детей. Эти дети разбиваются на непустые групы, и в каждой группе устраивают хоровод следующим образом: один из детей становится в центр, а остальные циклически упорядочиваются и водят хоровод вокруг него. При этом допускается хоровод из одного ребенка (он как звезда стоит в центре). Сколькими способами можно это сделать?

Очевидно, что составить хоровод из $n$ детей можно следующим ислом способов:
\[
	a_n = n\left(n-2\right)!
\]
(выбрать одного центрального, остальных циклически упорядочить), тогда получаем эпф:
\[
	F\left(x\right) = \sum_{i=0}^\infty i\left(i-2\right)! \frac{x^i}{i!} = \sum_{i=2}^\infty \frac{x^i}{i-1} = x\cdot ln\left(\frac{1}{1-x}\right)
\]
а согласно экспоненциальной формуле получаем следующее:
\[
	H\left(x\right) = \exp\left(F\left(x\right)\right) = exp\left(x\cdot ln\left(\frac{1}{1-x}\right)\right) = \frac{1}{\left(1-x\right)^x}
\]
теперь извлечем коэффициенты из этой формулы:
\[
	\begin{split}
		&H\left(x\right) = e^{F\left(x\right)} \Rightarrow H'\left(x\right) = e^{F\left(x\right)}F'\left(x\right) = \\
		& = H\left(x\right)F'\left(x\right) \Leftrightarrow \\
		& c_1 + c_2 x + c_3\frac{x^2}{2!} + ... = \left(c_0 + c_1 x + c_2 \frac{x^2}{2!} + ...\right)\left(a_1 + a_2x + a_3\frac{x^2}{2!}+...\right)
	\end{split}
\]
теперь по определению произведения эпф (и с учетом $c_0 = 1$):
\[
	\begin{split}
		& c_{n+1} = \sum_{i=0}^n \binom{n}{i} a_{i+1}\cdot c_{n-i} \Leftrightarrow a_{n+1} = c_{n+1} - \sum_{i=0}^{n-1}\binom{n}{i}a_{i+1}c_{n-i}
	\end{split}
\]
откуда получаем:
\begin{equation}
	c_{n+1}  = a_{n+1} + \sum_{i=1}^n \binom{n}{i} c_i a_{n-i+1}
\end{equation}
